package exercises.newcoder.solution;

import java.util.ArrayList;

/**
 * <a href="https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&&tqId=11156&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking">
 * JZ3 从尾到头打印链表</a>
 *
 * @author or2
 * @Description 输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
 * @create 2021年09月08日 时间: 17:37
 */
public class PrintListFromTailToHead {

    private static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

//    两遍遍历, 并逆置链表花费时间过长, 推荐直接使用容器, 最后逆置。
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
//        使用头结点, 头插法逆置链表
        ListNode head = new ListNode(0);
        ListNode p = listNode;
//        记录数组容量, 防止扩容
        int size = 0;
        while (p != null) {
            size++;
            ListNode next = p.next;
            p.next = head.next;
            head.next = p;
            p = next;
        }

        ArrayList<Integer> ans = new ArrayList<>(size);
        p = head.next;
        for (int i = 0; i < size; i++) {
            ans.add(i, p.val);
            p = p.next;
        }

        return ans;
    }
}
